#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;
/*HJJ QQ479287006
 *给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
 
输入：root = [2,1,3]
输出：true
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//TODO 方案2 遍历转换为数组 而且是有序的
//先序遍历 根左右
//中序便利 左跟又
//后续 左右跟
TreeNode *tempNode;

bool isValidBST_t(TreeNode *root) {
    if (!root)
        return true;


    //左子树为空 右边也为空
    if (!root->left && !root->right) {
        return true;
    }
    //如果其中一个为空
    if (!root->left) {
        return (root->right->val > root->val) && (tempNode->val < root->right->val) && isValidBST(root->right);
    }
    if (!root->right) {
        return (root->left->val < root->val) && (tempNode->val > root->left->val) && isValidBST(root->left);;
    }
    if (root->val <= root->left->val || root->val >= root->right->val) {
        return false;
    }

    return (root->val > root->left->val && root->val < root->right->val) &&
           (tempNode->val > root->left->val && tempNode->val < root->right->val) && isValidBST(root->left) &&
           isValidBST(root->right);
}

long long val = INT64_MIN; //妈的这个得longlong todo 树这边得重新看
//TODO 我擦 没看懂 哎我草 明白了 他就是中序遍历根上一个值比 哎我傻逼了
//这个题应该就是中序遍历求 是否是个有序序列 呜呜呜呜
bool isValidBST(TreeNode *root) {

    //这种写法没问题
    if (!root)
        return true;

    bool l = isValidBST(root->left);

    if (root->val <= val)
        return false;
    val = root->val;

    bool r = isValidBST(root->right);

    return l && r;
}






//一种错误的写法 没有遍历全
bool isValidBST(TreeNode* root) {

    if (!root)
        return true;

   bool  l=isValidBST(root->left);

    bool  r=isValidBST(root->right);


    if (root->left&&root->left->val>=root->val )
        return false;
    if ((root->right&&root->right->val<=root->val))
        return false;

    return l&&r;


}













